
from math import sqrt

def get_primes_under(max):
    primes = []
    for i in xrange(3, max, 2):
        is_prime = True
        max_factor = sqrt(i)
        for p in primes:
            if p > max_factor:
                break
            if i % p == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(i)
    return [2] + primes

primes = get_primes_under(100000)

def test_prime(n):
    max_factor = sqrt(n)
    for p in primes:
        if p > max_factor:
            break
        if n % p == 0:
            return False
    return True

from copy import copy

def pandigital_iter(numbers):
    if len(numbers) == 1:
        yield numbers[0]
    else:
        for i in numbers:
            remain_numbers = copy(numbers)
            remain_numbers.remove(i)
            for j in pandigital_iter(remain_numbers):
                yield int(str(i) + str(j))
    

for l in range(9, 3, -1):
    print 'finding prime in pandigital with length %d' % l
    for p in pandigital_iter(range(l, 0, -1)):
        if test_prime(p):
            print p
    
        